class Solution {
public:
    pair<int, int> dp[10][2][2000];
    unordered_map<int, int> ma;
    int countNumbersWithUniqueDigits(int n) {
        ma[1] = 0;
        int temp = 1;
        for (int i = 1; i <= 9; i++)
        {
            temp *= 2;
            ma[temp] = i;
        }
        return dfs(1, 1, n, (1 << 10) - 1);
    }
    int dfs(int pos, int free, int n, int t)
    {
        if (pos > n) return 1;
        if (dp[pos][free][t].second) return dp[pos][free][t].first;
        int ans = 0;
        if (free) ans += dfs(pos + 1, free, n, t);
        for (int i = t; i; i -= i & (-i))
        {
            int temp = i & (-i);
            if (!ma[temp] && free) continue;
            ans += dfs(pos + 1, 0, n, t - temp);
        }
        dp[pos][free][t].second = 1;
        return dp[pos][free][t].first = ans;
    }
};